Abstract: Privacy for microdata is common problem in external database and data publishing. K-anonymity is one technique to protect micro data against linkage and identification of records. While in previous k-anonymity algorithms exist for producing k-anonymous data, due to privacy issues, the common data from different sites cannot be shared directly and assumes existence of a public database that can be used to breach privacy. During anonymization process, public database are not utilized. In existing generalization algorithm creates anonymous table by using microdata table and focusing on identity disclosure, and k-anonymity model fails to protect attribute disclosure to some extent. In propose two new privacy protection models called (p, a)-sensitive k-anonymity and (p+, a)-sensitive k-anonymity, respectively. It is different from previous the p-sensitive, these new introduced models allow us to release a lot more information without compromising privacy. Moreover, we prove that the (p, a)-sensitive and (p+, a)-sensitive k-anonymity problems are NP-hard and include testing and heuristic generating algorithms to generate desired micro data table.

Keywords: Microdata, Privacy, k-anonymity, k-join-anonymity,(p, a)-sensitive k-anonymity and (p+,a)-sensitive k-anonymity.